package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/4/17 19:58
 * https://leetcode-cn.com/problems/minimum-genetic-mutation/
 */
public class Title433 {

    public static int minMutation(String start, String end, String[] bank) {
        Queue<String> queue = new LinkedList<>();
        Set<String> banks = new HashSet<>();
        banks.addAll(Arrays.asList(bank));
        if (!banks.contains(end)) {
            return -1;
        }
        //存放基因以及到达该基因的长度
        Map<String, Integer> visited = new HashMap<>();
        queue.offer(start);
        visited.put(start, 0);
        while (!queue.isEmpty()) {
            String gene = queue.poll();
            int path = visited.get(gene);
            //换每个基因的每一字符（广度）
            for (int i = 0; i < gene.length(); i++) {
                char[] chars = gene.toCharArray();
                char[] allChar = {'A', 'C', 'G', 'T'};
                for (int j = 0; j < allChar.length; j++) {
                    chars[i] = allChar[j];
                    String newGene = String.valueOf(chars);
                    if (newGene.equals(end)) {
                        return path + 1;
                    }
                    if (banks.contains(newGene) && !visited.containsKey(newGene)) {
                        visited.put(newGene, path + 1);
                        queue.offer(newGene);
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String[] s = {"AACCGGTA", "AACCGCTA", "AAACGGTA"};
        minMutation("AACCGGTT", "AAACGGTA", s);
    }
}
